
#include <unordered_map>
#include <vector>
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        //实现逻辑为通过前序遍历确定根节点，然后在中序遍历中找到当前节点的值，然后去构建左子树和右子树
        unordered_map<int,int> inordermap;
        for(int i = 0;i<vinOrder.size();i++)
        {
            inordermap[vinOrder[i]] = i;
        }
        return build(preOrder,0,preOrder.size()-1,vinOrder,0,vinOrder.size()-1,inordermap);
    }
private:
    TreeNode* build(vector<int>& pre,int prebegin,int prend,vector<int>& vin,int vinbegin,int vinend,unordered_map<int,int>&map)
    // prebegin是当前层的值，preend用于防止越界，map用于找到当前节点的值在中序遍历的哪一个位置
    // 然后使用这个值-vinbegin能够得到该节点左子树的数量，由此就能够知道这个节点的左子树的根节点的
    // 值为prebegin+1，而右子树根节点的值就是prebgien+leftnum+1，而该节点左子树的值的终点就是
    // prebegin+leftnum,至于中序遍历因为当前节点的位置为index那么左子树就是从vinbegin到index-1
    // 右子树的范围就是从index+1，到vinend
    {
        if(prebegin>prend||vinbegin>vinend)
        {
            return nullptr;
        }//这不是一个有效的范围，已经没有需要构造的节点了
        int val = pre[prebegin];
        TreeNode* root = new TreeNode(val);
        int index = map[val];
        int leftnum = index - vinbegin;//左子树的范围
        root->left = build(pre,prebegin+1,prebegin+leftnum,vin,vinbegin,index-1,map);
        root->right = build(pre,prebegin+1+leftnum,prend,vin,index+1,vinend,map);
        return root;
    }
};